const BinaryNode = require('./树节点/binarynode');
const BinaryTree = require('./binarytree')

// 二叉排序树
class BinarySortedTree extends BinaryTree {
    // 重写父类构造器
    constructor(arr) {
        super()
        for (let i = 0; i <= arr.length - 1; i++) {
            this._bstInsert(arr[i])
        }
    }
    // 插入
    _bstInsert(element) {
        let newNode = new BinaryNode(element)
        if (this.root === null) {
            this.root = newNode
        } else {
            this._bstInsertByRecursion(this.root, newNode)
        }
    }
    _bstInsertByRecursion(rootNode, newNode) {
        if (newNode.data < rootNode.data) {
            if (rootNode.left === null) {
                rootNode.left = newNode
            } else {
                this._bstInsertByRecursion(rootNode.left, newNode)
            }
        } else if (newNode.data > rootNode.data) {
            if (rootNode.right === null) {
                rootNode.right = newNode
            } else {
                this._bstInsertByRecursion(rootNode.right, newNode)
            }
        } else {}
    }
    // 查找
    search(key) {
        let p = this.root
        while (p !== null && key !== p.data) {
            if (key > p.data) {
                p = p.right
            } else {
                p = p.left
            }
        }
        return p
    }
    // 寻找最值，默认寻找最大值
    findExtreme(flag = true) {
        let p = this.root
        if (flag) {
            while (p.right !== null) {
                p = p.right
            }
        } else {
            while (p.left !== null) {
                p = p.left
            }
        }
        return p
    }
    // 寻找指定节点的父节点
    findParent(node) {
        let p = this.root
        let pFather = this.root
        while (p !== null && node !== p) {
            pFather = p
            if (node.data < p.data) {
                p = p.left
            } else {
                p = p.right
            }
        }
        return pFather
    }
    // 删除
    delete(key) {
        let keyNode = this.search(key)
        if (keyNode === null) throw new Error('找不到目标')
        this._deleteByRecursion(keyNode)
    }
    _deleteByRecursion(keyNode) {
        let father = this.findParent(keyNode)
        //叶子节点，找到父节点，直接删
        if (keyNode.left === null && keyNode.right === null) {
            if (father.left === keyNode) {
                father.left = null
            } else {
                father.right = null
            }
        }
        //仅有左子树
        else if (keyNode.left !== null && keyNode.right === null) {
            if (father.left === keyNode) {
                father.left = keyNode.left
            } else {
                father.right = keyNode.left
            }
        }
        //仅有右子树
        else if (keyNode.left === null && keyNode.right !== null) {
            if (father.left === keyNode) {
                father.left = keyNode.right
            } else {
                father.right = keyNode.right
            }
        }
        //左右子树均有
        /**
         * 需要找到目标删除节点的中序顺序下的直接后继
         * 使目标删除值改为此个直接后继值，并将直接后继删除
         * 根据后继的情况递归调用进行删除
         */
        else {
            // 寻找后继
            let pNext = keyNode.right
            while (pNext.left !== null) {
                pNext = pNext.left
            }
            // 替代
            keyNode.data = pNext.data
            // 删除直接后继pNext
            this._deleteByRecursion(pNext)
        }
    }
}

module.exports = BinarySortedTree





// let arr = [53, 17, 78, 9, 45, 23, 65, 94, 81, 88]
// let bst = new BinarySortedTree(arr)
// bst.inOrder()
// bst.delete(78)
// bst.inOrder()